class Solution:
	# @param matrix, a list of lists of 1 length string
	# @return an integer
	def maximalRectangle(self, matrix):
		row = len(matrix)
		if row == 0:
			return 0
		col = len(matrix[0])
		height = [0 for i in xrange(col)]
		left = [0 for i in xrange(col)]
		right = [col for i in xrange(col)]
		ans = 0
		for r in xrange(row):
			cur_left = 0
			cur_right = col
			# height
			for i in xrange(col):
				if matrix[r][i] == '1':
					height[i] += 1
				else:
					height[i] = 0
			# left
			for i in xrange(col):
				if matrix[r][i] == '1':
					left[i] = max(cur_left, left[i])
				else:
					cur_left = i + 1
					left[i] = 0
			# right
			for i in xrange(col-1,-1,-1):
				if matrix[r][i] == '1':
					right[i] = min(cur_right, right[i])
				else:
					cur_right = i
					right[i] = col
			# area
			for i in xrange(col):
				ans = max(ans, (right[i] - left[i]) * height[i])

		return ans

if __name__ == '__main__':
	so = Solution()
	a = [
		['0','0','1','0'],
		['0','1','1','0'],
		['0','1','1','0'],
		['0','0','1','0']
	]
	print(so.maximalRectangle(a))